
public class MedianMaintenance {
	
	//int []medianArray;
	int sum;

	public void ComputeMedian(int array[]){
		//medianArray = new int[array.length];
		MinHeap highHeap = new MinHeap(array.length/2 + 3);
		MaxHeap lowHeap = new MaxHeap(array.length/2 + 3);
		
		sum = 0;
		
		for(int i = 0; i < array.length; i++)
		{
			if(array[i] > highHeap.ExtractMin())
			{
				highHeap.Insert(array[i]);
			}
			else
			{
				lowHeap.Insert(array[i]);
			}
			
			//balance data between the two heaps
			if(highHeap.Size() - lowHeap.Size() >=  2)
			{
				lowHeap.Insert(highHeap.ExtractMin());
				highHeap.DeleteRoot();
			}
			else if(lowHeap.Size() - highHeap.Size() >= 2)
			{
				highHeap.Insert(lowHeap.ExtractMax());
				lowHeap.DeleteRoot();
			}
			
			if(i/2 + 1 > lowHeap.Size())
			{
				sum += highHeap.ExtractMin();
			}
			else
			{
				sum += lowHeap.ExtractMax();
			}
		}
	}
	
	public void PrintMedianList(){
		/*for(int i = 0; i < medianArray.length; i++)
		{
			System.out.print(i + 1 + ":\t" + medianArray[i] + "\n");
		}*/
		System.out.print("median sum is " + sum + "\n");
	}
}
